1. Field of the Invention
This invention relates to apparatus and methods for efficiently computing and recomputing hash values for strings.
2. Background of the Invention
Sequences of characters, commonly referred to as “strings,” are used extensively in modern-day programming languages. For example, the Java runtime uses the String class extensively. In the Java runtime, every string has a hash value computed over the contents of the string which is used to identify the string. Because strings may be long, computing the hash value for strings can be computationally expensive. Furthermore, because string objects are used heavily by the Java Virtual Machine (JVM) as well as applications running on the JVM, the hash function is invoked frequently. Operation of the hash function, therefore, consumes significant computational resources.
Each time a string is modified, such as by concatenating a substring to an existing string, removing a substring from the beginning or end of an existing string, or modifying a substring within an existing string that preserves the length of the string, the hash value of the modified string needs to be recomputed. Like the original hash value computation, recomputing the hash value can be computationally expensive since the hash value is typically recomputed from scratch. Because string modifications may occur frequently, such recomputations may also occur frequently, consuming significant computational resources.
In view of the foregoing, what are needed are apparatus and methods to efficiently compute and recompute hash values for strings and other sequences of characters. Ideally, such apparatus and methods may be used to efficiently recompute hash values for modified strings without having to start from scratch.